import java.util.HashMap;
import java.util.Map;

public class MinWindow {
    public static void main(String[] args) {
        String testS1="ADOBECODEBANC";
        String testT1="ABC";
        String testS2="a";
        String testT2="a";
        String testS3="a";
        String testT3="aa";
        String testS4="aab";
        String testT4="aab";
        MinWindow minWindow = new MinWindow();
//        System.out.println(minWindow.minWindowTwoPoint3(testS1, testT1));
//        System.out.println(minWindow.minWindowTwoPoint3(testS2, testT2));
//        System.out.println(minWindow.minWindowTwoPoint3(testS3, testT3));
        System.out.println(minWindow.minWindowTwoPoint3(testS4, testT4));

    }
    public String minWindow(String s, String t) {
        String result ="";
        Map<Character,Integer> tCountMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            tCountMap.put(t.charAt(i),tCountMap.getOrDefault(t.charAt(i),0)+1);
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+t.length()-1; j <s.length() ; j++) {
                if(!result.isEmpty() && !(result.length() > j-i+1)){
                    continue;
                }
                Map<Character,Integer> sCountMap = new HashMap<>();
                for (int k = i; k <= j; k++) {
                    sCountMap.put(s.charAt(k),sCountMap.getOrDefault(s.charAt(k),0)+1);
                }
                boolean rTemp = true;
                for (Character c : tCountMap.keySet()) {
                    if(sCountMap.getOrDefault(c,0)<tCountMap.get(c)){
                        rTemp = false;
                    }
                }
                if(rTemp){
                    String substring = s.substring(i, j + 1);
                    if(result.isEmpty() || result.length() > substring.length()) {
                        result = substring;
                    }
                }
            }
        }
        return result;

    }

    public String minWindowTwoPoint(String s, String t) {
        String result ="";
        Map<Character,Integer> tCountMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            tCountMap.put(t.charAt(i),tCountMap.getOrDefault(t.charAt(i),0)+1);
        }
        int slow = 0;
        int fast = t.length()-1;
        while(slow < s.length() && fast<s.length()){
            Map<Character,Integer> sCountMap = new HashMap<>();
            for (int i = slow; i <= fast ; i++) {
              sCountMap.put(s.charAt(i),sCountMap.getOrDefault(s.charAt(i),0)+1);
            }
            boolean rTemp = true;
            for (Character c : tCountMap.keySet()) {
                if(sCountMap.getOrDefault(c,0)<tCountMap.get(c)){
                    rTemp = false;
                }
            }
            if(rTemp){
                String substring = s.substring(slow, fast + 1);
                if(result.isEmpty() || result.length() > substring.length()) {
                    result = substring;
                }
                slow++;
            }else{
                fast ++;
            }
        }
        return result;
    }

    /**
     * 利用汉明距离
     * @param s
     * @param t
     * @return
     */
    public String minWindowTwoPoint2(String s, String t) {
        String result ="";
        Map<Character,Integer> tCountMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            tCountMap.put(t.charAt(i),tCountMap.getOrDefault(t.charAt(i),0)+1);
        }
        int slow = 0;
        int fast = 0;
        Map<Character,Integer> sCountMap = new HashMap<>();
        while( fast<s.length()){
            if(tCountMap.containsKey(s.charAt(fast))){
                sCountMap.put(s.charAt(fast),sCountMap.getOrDefault(s.charAt(fast),0)+1);
            }
            boolean rTemp = true;
            while(rTemp){
                for (Character c : tCountMap.keySet()) {
                    if(sCountMap.getOrDefault(c,0)<tCountMap.get(c)){
                        rTemp = false;
                    }
                }
                if(rTemp){
                    String substring = s.substring(slow, fast + 1);
                    if(result.isEmpty() || result.length() > substring.length()) {
                        result = substring;
                    }
                    if(tCountMap.containsKey(s.charAt(slow))){
                        sCountMap.put(s.charAt(slow),sCountMap.getOrDefault(s.charAt(slow),0)-1);
                    }
                    slow++;
                }
            }
            fast++;
        }
        return result;
    }
    public String minWindowTwoPoint3(String s, String t) {
        String result ="";
        Map<Character,Integer> tCountMap = new HashMap<>();
        int count = 0;
        for (int i = 0; i < t.length(); i++) {
            tCountMap.put(t.charAt(i),tCountMap.getOrDefault(t.charAt(i),0)+1);
        }
        int slow = 0;
        int fast = 0;
        Map<Character,Integer> sCountMap = new HashMap<>();
        while( fast<s.length()){
            if(tCountMap.containsKey(s.charAt(fast))){
                int tempCount = sCountMap.getOrDefault(s.charAt(fast), 0) + 1;
                sCountMap.put(s.charAt(fast), tempCount);
                if(tempCount <= tCountMap.get(s.charAt(fast))) count++;
            }
            while( slow<=fast && count==t.length()){
                String substring = s.substring(slow, fast + 1);
                if(result.isEmpty() || result.length() > substring.length()) {
                    result = substring;
                }
                if(tCountMap.containsKey(s.charAt(slow))){
                    int tempCount = sCountMap.getOrDefault(s.charAt(slow), 0) - 1;
                    sCountMap.put(s.charAt(slow), tempCount);
                    if(tempCount < tCountMap.get(s.charAt(slow))) count--;
                }
                slow++;
            }
            fast++;
        }
        return result;
    }
}
